package leetcode.listnode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
 * 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
 *
 * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 *
 * 示例 1:
 *
 * 给定链表 1->2->3->4, 重新排列为 1->4->2->3.
 * 示例 2:
 *
 * 给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
 */
public class ReorderList {

    public void reorderList(ListNode head) {
        ListNode node = head.next;
        Deque<ListNode> deque = new LinkedList<>();
        while (node != null){
            deque.add(node);
            node = node.next;
        }

        int index = 2;
        ListNode result = head;
        while (deque.size() != 0){
            if (index % 2 == 1){
                System.out.println(deque.getFirst().val);
                result.next = deque.getFirst();
                deque.removeFirst();
            }else if(index % 2 == 0){
                System.out.println(deque.getLast().val);
                result.next = deque.getLast();
                deque.removeLast();
            }
            result = result.next;
            index++;
        }
        result.next = null;
    }

}
